package foundation.tree.binaryTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author hang an
 * @since 2025/7/11
 */
public class 二叉树最大宽度 {
    int res = 1;
    Map<Integer, Long> map = new HashMap<>();

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        dfs(root, 1, 1);
        return res;
    }

    private void dfs(TreeNode node, int deep, long data) {
        if (node == null) return;
        if (!map.containsKey(deep)) {
            map.put(deep, data);
        }
        res = Math.max(res, (int) (data - map.get(deep) + 1));
        if (node.left != null) dfs(node.left, deep + 1, data << 1);
        if (node.right != null) dfs(node.right, deep + 1, data << 1 | 1);
    }
}
